High Efficiency Video Coding (HEVC) is a new coding standard that has been developed in recent years. In the High Efficiency Video Coding (HEVC) system, the fixed-size macroblock of H.264/AVC is replaced by a flexible block, named coding unit (CU). Pixels in the CU share the same coding parameters to improve coding efficiency. A CU may begin with a largest CU (LCU), which is also referred as coded tree unit (CTU) in HEVC. In addition to the concept of coding unit, the concept of prediction unit (PU) is also introduced in HEVC. Once the splitting of CU hierarchical tree is done, each leaf CU is further split into one or more prediction units (PUs) according to prediction type and PU partition.
Along with the High Efficiency Video Coding (HEVC) standard development, the development of extensions of HEVC has also started. The HEVC extensions include screen content coding (SCC). Due to specific characteristics of screen contents, coding tools have been developed and demonstrate significant gains in coding efficiency. Among them, the colour index coding (a.k.a. major colour based coding) techniques represent block of pixels using indices to the palette (major colours), and encode the palette and the indices by exploiting spatial redundancy. While the total number of possible colour combinations is huge, the number of colours in an area of picture is usually very limited for typical screen contents. Therefore, the colour index coding becomes very effective for screen content materials. Related key colour index coding techniques are briefly reviewed as follows.
Palette Coding
During the development of HEVC range extensions (RExt), several proposals have been disclosed to address palette-based coding. For example, a palette prediction and sharing technique is disclosed in JCTVC-N0247 (Guo et al., “RCE3: Results of Test 3.1 on Palette Mode for Screen Content Coding”, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 14th Meeting: Vienna, AT, 25 Jul.-2 Aug. 2013 Document: JCTVC-N0247) and JCTVC-O0218 (Guo et al., “Evaluation of Palette Mode Coding on HM-12.0+RExt-4.1”, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 15th Meeting: Geneva, CH, 23 Oct.-1 Nov. 2013, Document: JCTVC-O0218). In JCTVC-N0247 and JCTVC-00218, the palette of each colour component is constructed and transmitted. The palette can be predicted (or shared) from its left neighbouring CU to reduce the bitrate. All pixels within the given block are then coded using their palette indices. An example of encoding process according to JCTVC-N0247 is shown as follows.                1. Transmission of the palette: the colour index table (also called palette table) size is first transmitted followed by the palette elements (i.e., colour values).        2. Transmission of pixel values: the pixels in the CU are encoded in a raster scan order. For each group of one or more pixels, a flag for a run-based mode is first transmitted to indicate whether the “copy index mode” or “copy above mode” is being used.                    2.1 “Copy index mode”: In the copy index mode, a palette index is first signalled followed by “palette_run” (e.g., M) representing the run value. The term palette_run may also be referred as pixel_run in this disclosure. The run value indicates that a total of M samples are all coded using copy index mode. No further information needs to be transmitted for the current position and the following M positions since they have the same palette index as that signalled in the bitstream. The palette index (e.g., i) may also be shared by all three colour components, which means that the reconstructed pixel values are (Y, U, V)=(paletteY[i], paletteU[i], paletteV[i]) for the case of YUV colour space.            2.2 “Copy above mode”: In the copy above mode, a value “copy_run” (e.g. N) is transmitted to indicate that for the following N positions (including the current one), the palette index is the same as the corresponding palette index in the row above.                        3. Transmission of residue: the palette indices transmitted in Stage 2 are converted back to pixel values and used as the prediction. Residue information is transmitted using HEVC residual coding and is added to the prediction for the reconstruction.        
Both “copy index mode” and “copy above mode” are referred as copy modes for palette index coding in this disclosure. Besides, the palette mode is also referred to as palette coding mode in the following descriptions.
In JCTVC-N0247, palette of each component are constructed and transmitted. The palette can be predicted (shared) from its left neighbouring CU to reduce the bitrate. In JCTVC-O0218, each element in the palette is a triplet, which represents a specific combination of the three colour components. Furthermore, the predictive coding of palette across CU is removed.
Major-Colour-Based (or Palette) Coding
Another palette coding technique similar to JCTVC-O0218 has also been disclosed. Instead of predicting the entire palette table from the left CU, individual palette colour entry in a palette is predicted from the exact corresponding palette colour entry in the above CU or left CU.
For transmission of pixel palette index values, a predictive coding method is applied on the indices as disclosed in JCTVC-O0182 (Guo et al., “AHG8: Major-colour-based screen content coding”, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 15th Meeting: Geneva, CH, 23 Oct.-1 Nov. 2013, Document: JCTVC-O0182). Three types of line modes, i.e., horizontal mode, vertical mode and normal mode are used for coding each index line. In the horizontal mode, all the indices in the same line have the same value. If the value is the same as the first pixel of the above pixel line, only line mode signalling bits are transmitted. Otherwise, the index value is also transmitted. In the vertical mode, it indicates that the current index line is the same with the above index line. Therefore, only line mode signalling bits are transmitted. In normal mode, indices in a line are predicted individually. For each index position, the left or above neighbours is used as a predictor, and the prediction symbol is transmitted to the decoder.
Furthermore, pixels are classified into major colour pixels (with palette indices pointing to the palette colours) and escape pixel according to JCTVC-O0182. For major colour pixels, the pixel value is reconstructed according to the major colour index (i.e., palette index) and palette table in the decoder side. For escape pixel, the pixel value is further signalled in the bitstream.
Palette Table Signalling
In the reference software of screen content coding (SCC) standard, SCM-2.0 (Joshi et al., Screen content coding test model 2 (SCM 2), Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 18th Meeting: Sapporo, JP, July 2014, Document No.: JCTVC-R1014), an improved palette scheme is integrated in JCTVC-R0348 (Onno, et al., Suggested combined software and text for run-based palette mode, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 18th Meeting: Sapporo, JP, July 2014, Document No.: JCTVC-R0348). The palette table of previous palette-coded CU is used as a predictor for current palette table coding. In palette table coding, the current palette table is signalled by choosing which palette colours in the previous coded palette table (palette predictor) are reused, or by transmitting new palette colours. The size of the current palette is set as the size of the predicted palette (i.e., numPredPreviousPalette) plus the size of the transmitted palette (i.e., num_signalled_palette_entries). The predicted palette is a palette derived from the previously reconstructed palette coded CUs. When coding the current CU as a palette mode, those palette colours that are not predicted using the predicted palette are directly transmitted in the bitstream (i.e., signalled entries).
An example of palette updating is shown as follows. In this example, the current CU is coded as palette mode with a palette size equal to six. Three of the six major colours are predicted from the palette predictor (numPredPreviousPalette=3) and three are directly transmitted through the bitstream. The transmitted three colours can be signalled using the exemplary syntax shown below.                num_signalled_palette_entries=3        for(cIdx=0; cIdx<3; cIdx++)//signal colours for different components                    for(i=0; i<num_signalled_palette_entries; i++)            palette_entries[cIdx][numPredPreviousPalette+i]                        
Since the palette size is six in this example, the palette indices from 0 to 5 are used to indicate the major colour entries in the palette colour table. The 3 predicted palette colours are represented with indices 0 to 2. Accordingly, three new palette entries are transmitted for indexes 3 through 5.
In SCM-2.0, if the wavefront parallel processing (WPP) is not applied, the palette predictor table is initialized (reset) at the beginning of each slice or at the beginning of each tile. If the WPP is applied, the last coded palette table is not only initialized (reset) at the beginning of each slice or at the beginning of each tile, but also initialized (reset) at the beginning of each CTU row.
Palette Index Map Scan Order
In SCM-3.0 palette mode coding, the traverse scan is used for index map coding as shown in FIG. 1A to FIG. 1C. FIG. 1A shows a horizontal traverse scan for an 8×8 block. In traverse scan, the scan for even rows is from left to right, and the scan for odd rows is from right to left. The traverse scan is applied for all block sizes in palette mode. FIG. 1B shows a reverse horizontal traverse scan for an 8×8 block. FIG. 1C shows a rotated (i.e., 180°) horizontal traverse scan for an 8×8 block respectively.
Palette Index Map Coding in SCM-4.0
In the palette mode coding according to SCM-4.0 (Joshi et al., Screen content coding test model 4 (SCM 4), JCTVC-T1014, ITU-T SG16 WP3 and ISO/IEC JTC1/SC29/WG11, 20th Meeting: Geneva, CH, February 2015, Document: JCTVC-T1014), the palette indices are grouped and coded in front (i.e., before palette_run_mode and palette_run coding), and the escape pixels are coded at the end. The palette_run_mode and palette_run are coded between palette indices and escape pixels.
For palette run syntax, the binarization of associated symbols is divided into the most significant bit (MSB) index and the refinement bits of its value in a binary form. The MSB index for value 0 is assigned to −1. The resulting codeword is a concatenation of a prefix part and a suffix part. The prefix part represents the MSB index of a symbol value plus 1, denoted by msb_id_plus1, in a unary code or a truncated unary code if the maximal syntax value is known. msb_id_plus1 of a unsigned symbol x is given by
      msb_id    ⁢    _plus    ⁢                  ⁢    1    =      {                                                                      Floor                ⁢                                                                  ⁢                                  (                                      Log                    ⁢                                                                                  ⁢                    2                    ⁢                                          (                      x                      )                                                        )                                            +              1                                                                                            if                  ⁢                                                                          ⁢                  x                                >                0                            ;                                                                          0              ,                                            otherwise                              .      
The suffix bin part represents the refinement bits and is present if msb_id_plus 1>1. The value of refinement bits, denoted by refinement_bits, is binarized by a fixed-length binary code with the string length equal to msb_id_plus1−1 or a truncated binary code if the maximal syntax value is known. The decoded syntax value x is given by
  x  =      {                                                                                                            F                    ⁡                                          (                                                                        1                          ⁢                                                                                                          ⁢                                                      <<                            (msb_id_plus                                                    ⁢                                                                                                          ⁢                          1                                                -                        1                                            )                                                        )                                +                refinement_bits                            ,                                                                                            if                  ⁢                                                                          ⁢                  msb_id                  ⁢                  _plus                  ⁢                                                                          ⁢                  1                                >                1                            ;                                                                                          msb_id                ⁢                _plus                ⁢                                                                  ⁢                1                            ,                                            otherwise                              .      